package com.lfg.leetcode.leetcode300;


import java.util.*;

public class No381RandomizedCollection {
    public static void main(String[] args) {
        RandomizedCollection obj = new RandomizedCollection();
        System.out.println(obj.insert(0));
        System.out.println(obj.remove(0));
        System.out.println(obj.insert(-1));
        System.out.println(obj.remove(0));
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
    }


}

class RandomizedCollection {

    Map<Integer, LinkedHashSet<Integer>> data;
    List<Integer> list;
    Random rand;

    public RandomizedCollection() {
        data = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        boolean ret = false;
        LinkedHashSet<Integer> array = data.get(val);
        if (array == null) {
            array = new LinkedHashSet<>();
            data.put(val, array);
            ret = true;
        }
        list.add(val);
        array.add(list.size() - 1);
        return ret;
    }

    public boolean remove(int val) {
        LinkedHashSet<Integer> array = data.get(val);
        if (array == null || array.size() == 0) {
            return false;
        }
        Integer index = array.iterator().next();
        int lastIndex = list.size() - 1;
        array.remove(index);
        if (index != lastIndex) {
            Integer element = list.get(lastIndex);
            list.set(index, element);
            LinkedHashSet<Integer> array2 = data.get(element);
            array2.remove(lastIndex);
            array2.add(index);
        }
        list.remove(lastIndex);
        return true;
    }

    public int getRandom() {
        int index = rand.nextInt(list.size());
        return list.get(index);
    }
}


